{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# **Implementing Red/Black Trees (RBTs)**\n",
    "#### Carl Ehrett, Stephen Peele"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### **1. Why care about red/black trees?**\n",
    "\n",
    "#### Binary search trees\n",
    "A red/black tree (RBT) is a type of binary search tree (BST). Recall that a BST has the following properties:\n",
    "- Each node may have up to two children. \n",
    "- All left descendants of a node are less than that node. \n",
    "- All right descendants of a node are greater than that node.\n",
    "- Insert, delete, and lookup are all $\\mathcal O (h)$ where $h$ is the height of the tree.\n",
    "- In average cases, $h$ is proportional to $\\log n$, making the above operations $\\mathcal O (\\log n)$.\n",
    "\n",
    "#### Motivation to use red/black trees\n",
    "\n",
    "- Though the complexity of insert, delete and lookup for a BST are $\\mathcal O(\\log n)$ in the average case, they are $\\mathcal{O}(n)$ in the worst case. \n",
    "- It may be the case that a BST is highly unbalanced either inherently or through a sequence of operations.\n",
    "- If the depth of the tree is becomes too great, then operations may become very inefficient.\n",
    "- Is there a way to maintain the \"balance\" in a BST and improve the worst case complexity? *Yes!*\n",
    "- This leads to the red/black tree.\n",
    "\n",
    "#### What is a red/black tree?\n",
    "\n",
    "A red/black tree is a BST with the following additional properties:\n",
    "- Every node has a color -- red or black.\n",
    "- Every red node that is not a leaf has only black children.\n",
    "- Every path from the root to a leaf contains the same number of black nodes. \n",
    "- The root node is black.\n",
    "\n",
    "After any operation on a RBT, these properties have to be restored (if necessary). These constraints force the BST to maintain \"balance\" -- the depth is on average roughly $2\\log n$ (Sedgewick, 2008). For example, a RBT with 500 random elements is, on average, about twelve (12) nodes deep! \n",
    "\n",
    "*Visualization*: https://www.cs.usfca.edu/~galles/visualization/RedBlack.html\n",
    "\n",
    "#### What is gained?\n",
    "\n",
    "- Very clearly, a balanced tree lends itself to more efficient operations. \n",
    "- The RBT constraints force the BST to maintain some sense of balance (not to imply perfect symmetry)!\n",
    "- All operations on a RBT are worst-case $\\mathcal{O}(\\log n)$, certainly a marked improvement from $\\mathcal{O}(n)$.\n",
    "\n",
    "#### Real Instances of RBTs\n",
    "- One use: the ext3 file system uses RBTs to keep track of directory entries in the Linux kernel.\n",
    "\n",
    "#### Main results\n",
    "- Implemented RBTs in Python.\n",
    "- Visually, the balance in a RBT versus a BST for identical data is distinctly clear. \n",
    "- Timing tests demonstrate that the RBTs are indeed more efficient than BSTs in the worst-case.\n",
    "- For average case, the RBT may actually be slower than the BST since the RBT has more computational overhead (as tested on SageMathCloud)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### **2. Background: Tree nodes, binary search trees, and plot_tree**\n",
    "In this section, we establish code for tree nodes, binary search trees, and plot_tree (a function for plotting trees)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "from pylab import rcParams"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class TreeNode(object):\n",
    "    def __init__(self, data, left_child = None, right_child = None):\n",
    "        self.data  = data\n",
    "        self.left  = left_child\n",
    "        self.right = right_child\n",
    "        self.color = 1 # 1 for red, 0 for black \n",
    "    \n",
    "    def traverse_infix(self, result = None):\n",
    "        if result == None:\n",
    "            result = []\n",
    "            \n",
    "        if self.left:\n",
    "            self.left.traverse_infix(result)\n",
    "            \n",
    "        result.append(self.data)\n",
    "        \n",
    "        if self.right:\n",
    "            self.right.traverse_infix(result)\n",
    "            \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# create a graphical representation of a binary tree (plot_tree, below, uses plot_node)\n",
    "def plot_node(node, rb = True, level = 1, posx = 0, posy = 0):\n",
    "    \n",
    "    width = 2000.0 * (0.5**(level)) # This will be used to space nodes horizontally\n",
    "    if node.color == 0 or rb == False: plt.text(posx, posy, str(node.data), horizontalalignment='center',color='k',fontsize=10)\n",
    "    else: plt.text(posx, posy, str(node.data), horizontalalignment='center',color='r',fontsize=10)\n",
    "    \n",
    "    if node.left:\n",
    "        px = [posx, posx-width]\n",
    "        py = [posy-1, posy-15]\n",
    "        if node.left.color == 0 or rb==False: plt.plot(px,py,'k-')\n",
    "        else: plt.plot(px,py,'r-')\n",
    "        plot_node(node.left, rb, level+1, posx-width, posy-20)\n",
    "    \n",
    "    if node.right:\n",
    "        plot_node(node.right, rb, level+1, posx+width, posy-20)\n",
    "        px = [posx, posx+width]\n",
    "        py = [posy-1, posy-15]\n",
    "        if node.right.color == 0 or rb==False:  plt.plot(px,py,'k-')\n",
    "        else: plt.plot(px,py,'r-')\n",
    "\n",
    "def plot_tree(node, figsize=(10,6)):\n",
    "    if node.color == 1: rb=False\n",
    "    else: rb=True\n",
    "    rcParams['figure.figsize'] = figsize\n",
    "    fig, ax = plt.subplots()\n",
    "    ax.axis('off')\n",
    "    plot_node(node,rb)\n",
    "    plt.show()\n",
    "    \n",
    "##### Create also a normal, black-only version for testing\n",
    "# create a graphical representation of a binary tree (plot_tree uses plot_node)\n",
    "def plot_nodeBW(node, level = 1, posx = 0, posy = 0):\n",
    "    \n",
    "    width = 2000.0 * (0.5**(level))\n",
    "    if node != None: \n",
    "        plt.text(posx, posy, str(node.data), horizontalalignment='center',color='k',fontsize=10)\n",
    "        if node.left:\n",
    "            px = [posx, posx-width]\n",
    "            py = [posy-1, posy-18]\n",
    "            plt.plot(px,py,'k-')\n",
    "            plot_node(node.left, level+1, posx-width, posy-20)\n",
    "    \n",
    "        if node.right:\n",
    "            plot_node(node.right, level+1, posx+width, posy-20)\n",
    "            px = [posx, posx+width]\n",
    "            py = [posy-1, posy-18]\n",
    "            plt.plot(px,py,'k-')\n",
    "    else: plt.text(posx, posy, 'NONE', horizontalalignment='center',color='k',fontsize=10)\n",
    "    \n",
    "    \n",
    "        \n",
    "def plot_treeBW(node, figsize=(10,6)):\n",
    "    rcParams['figure.figsize'] = figsize\n",
    "    fig, ax = plt.subplots()\n",
    "    ax.axis('off')\n",
    "    plot_nodeBW(node)\n",
    "    plt.show()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "## Below is code to implement a (colorless) binary search tree.\n",
    "class BST(object):\n",
    "    def __init__(self):\n",
    "        self.tree = None\n",
    "    \n",
    "    def _find_node(self, node, obj):\n",
    "        if node == None:\n",
    "            return None\n",
    "        if node.data == obj:\n",
    "            return node\n",
    "        if obj < node.data:\n",
    "            return self._find_node(node.left, obj)\n",
    "        else: # so obj > node.data\n",
    "            return self._find_node(node.right, obj)\n",
    "    \n",
    "    def is_element(self, obj):\n",
    "        node = self._find_node(self.tree, obj)\n",
    "        if node:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "    def _insert(self, node, obj):\n",
    "        if obj < node.data:\n",
    "            if node.left:\n",
    "                self._insert(node.left, obj)\n",
    "            else:\n",
    "                node.left = TreeNode(obj)\n",
    "        elif obj > node.data:\n",
    "            if node.right:\n",
    "                self._insert(node.right, obj)\n",
    "            else:\n",
    "                node.right = TreeNode(obj)\n",
    "        # do nothing if equal\n",
    "    \n",
    "    def insert(self, obj):\n",
    "        if self.tree == None:\n",
    "            self.tree = TreeNode(obj)\n",
    "        else:\n",
    "            self._insert(self.tree, obj)\n",
    "        \n",
    "    def _replace_child(self, node, old, new):\n",
    "        if node==None:\n",
    "            self.tree = new\n",
    "        elif node.left == old:\n",
    "            node.left = new\n",
    "        elif node.right == old:\n",
    "            node.right = new\n",
    "        else:\n",
    "            assert(false)\n",
    "    \n",
    "    def _delete_node(self, parent, node, obj):\n",
    "        if node == None:\n",
    "            return\n",
    "        if obj < node.data:\n",
    "            # traverse left\n",
    "            self._delete_node(node,node.left, obj)\n",
    "        elif obj > node.data:\n",
    "            # traverse right\n",
    "            self._delete_node(node,node.right, obj)\n",
    "        elif node.data == obj:\n",
    "            if node.left == None:\n",
    "                # no left child, so replace node by its right child\n",
    "                self._replace_child(parent, node, node.right)\n",
    "            elif node.right == None:\n",
    "                # no right child, so replace node by its left child\n",
    "                self._replace_child(parent, node, node.left)\n",
    "            else: # node has two children:\n",
    "                parent = node\n",
    "                pred   = node.left\n",
    "                while pred.right: \n",
    "                    parent = pred\n",
    "                    pred   = pred.right\n",
    "                node.data=pred.data\n",
    "                self._replace_child(parent, pred, pred.left)\n",
    "                \n",
    "                # find predecessor pred, replace node.data with it:\n",
    "                # ...\n",
    "                \n",
    "                # now replace the predecessor by its left child:\n",
    "                # ...\n",
    "    \n",
    "    def delete(self, obj):\n",
    "        if self.tree == None:\n",
    "            return\n",
    "        self._delete_node(None, self.tree, obj)        \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### **3. Left-leaning Red/Black Trees**\n",
    "In this section, we implement a class for left-leaning red/black trees, a la Sedgewick 2008."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "### Here is the LLRBT implementation.\n",
    "class RBT(object):\n",
    "    def __init__(self):\n",
    "        \"\"\"Initialize a red/black tree.\"\"\"\n",
    "        self.tree = None\n",
    "    \n",
    "    def _find_node(self, node, obj):\n",
    "        \"\"\"Private function for traversing tree to lookup obj.\"\"\"\n",
    "        if node == None:\n",
    "            return None\n",
    "        if node.data == obj:\n",
    "            return node\n",
    "        if obj < node.data:\n",
    "            return self._find_node(node.left, obj)\n",
    "        else: # so obj > node.data\n",
    "            return self._find_node(node.right, obj)\n",
    "    \n",
    "    def is_element(self, obj):\n",
    "        \"\"\"Public function to lookup obj. Returns True iff obj is in tree.\"\"\"\n",
    "        node = self._find_node(self.tree, obj)\n",
    "        if node:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "    def _insert(self, node, obj, ):\n",
    "        \"\"\"Private function for traversing tree to insert obj. Perform color changes on the way down, and rotations on the way up, to preserve RBT properties.\"\"\"\n",
    "        if node == None: return TreeNode(obj) # If we've arrived at a terminus, then make new node.\n",
    "        if self._isRed(node.left) and self._isRed(node.right): self._colorFlip(node) # If both children are red, then colorflip\n",
    "        if obj < node.data: node.left = self._insert(node.left,obj)\n",
    "        elif obj > node.data: node.right = self._insert(node.right,obj)\n",
    "        if self._isRed(node.right) and not self._isRed(node.left): node = self._rotateLeft(node)\n",
    "        if self._isRed(node.left) and self._isRed(node.left.left): node = self._rotateRight(node)\n",
    "        return node\n",
    "    \n",
    "    def insert(self, obj):\n",
    "        \"\"\"Public function to insert obj in tree.\"\"\"\n",
    "        if self.tree == None:\n",
    "            self.tree = TreeNode(obj)\n",
    "        else:\n",
    "            self.tree = self._insert(self.tree, obj)\n",
    "            self.tree.color = 0 # The root must always be black\n",
    "            \n",
    "    def _colorFlip(self,node): # flip the colors of node and its children\n",
    "        \"\"\"Flip the color of node and its children. Used internally to preserve RBT properties.\"\"\"\n",
    "        node.color       = 1 - node.color\n",
    "        if node.left: node.left.color  = 1 - node.left.color\n",
    "        if node.right: node.right.color = 1 - node.right.color\n",
    "    \n",
    "    def _rotateRight(self,node): # rotate right\n",
    "        \"\"\"Rotate node right, preserving RBT properties.\"\"\"\n",
    "        originalLeft = node.left\n",
    "        node.left = originalLeft.right\n",
    "        originalLeft.right = node\n",
    "        originalLeft.color = node.color\n",
    "        node.color = 1\n",
    "        return originalLeft\n",
    "        \n",
    "    def _rotateLeft(self,node): # rotate left\n",
    "        \"\"\"Rotate node left, preserving RBT properties.\"\"\"\n",
    "        originalRight = node.right\n",
    "        node.right = originalRight.left\n",
    "        originalRight.left = node\n",
    "        originalRight.color = node.color\n",
    "        node.color = 1\n",
    "        return originalRight\n",
    "    \n",
    "    def _isRed(self,node): \n",
    "        \"\"\"Returns True iff node is red.\"\"\"\n",
    "        if node == None: return 0 # Nil nodes are black\n",
    "        return(node.color==1)\n",
    "        \n",
    "    def _delete_node(self, node, obj):\n",
    "        \"\"\"Private function for traversing tree to delete obj. Perform movements and rotations during traversal to preserve RBT properties.\"\"\"\n",
    "        if node == None: return node \n",
    "        if obj < node.data:\n",
    "            if node.left == None or (not self._isRed(node.left) and not self._isRed(node.left.left)):\n",
    "                node = self._moveRedLeft(node)\n",
    "            node.left = self._delete_node(node.left, obj)\n",
    "        else:\n",
    "            if self._isRed(node.left): node = self._rotateRight(node) \n",
    "            if obj == node.data and node.right == None: \n",
    "                return None\n",
    "            if node.right == None or (not self._isRed(node.right) and not self._isRed(node.right.left)): \n",
    "                node = self._moveRedRight(node)\n",
    "            if obj == node.data:\n",
    "                node.data = self._min(node.right)\n",
    "                node.right = self._deleteMin(node.right)\n",
    "            else: node.right = self._delete_node(node.right, obj)\n",
    "        return self.fixUp(node)\n",
    "    \n",
    "    def _deleteMin(self,node):\n",
    "        \"\"\"Delete the minimum descendant of node. Performs movements during traversal to preserve RBT properties.\"\"\"\n",
    "        if node.left == None: return None\n",
    "        if node.left == None or (not self._isRed(node.left) and not self._isRed(node.left.left)):\n",
    "            node = self._moveRedLeft(node)\n",
    "        node.left = self._deleteMin(node.left)\n",
    "        return self.fixUp(node)\n",
    "    \n",
    "    def _min(self,node): \n",
    "        \"\"\"Return the data of the minimum descendant of node.\"\"\"\n",
    "        while node.left != None: node = node.left \n",
    "        if node == None: return None \n",
    "        else: return node.data \n",
    "        \n",
    "    def _moveRedLeft(self, node):\n",
    "        \"\"\"Moves red node left. Used internally to preserve RBT properties.\"\"\"\n",
    "        self._colorFlip(node)\n",
    "        if node.right and self._isRed(node.right.left):\n",
    "            node.right = self._rotateRight(node.right)\n",
    "            node = self._rotateLeft(node)\n",
    "            self._colorFlip(node)\n",
    "        return node\n",
    "    \n",
    "    def _moveRedRight(self, node):\n",
    "        \"\"\"Moves red node right. Used internally to preserve RBT properties.\"\"\"\n",
    "        self._colorFlip(node)\n",
    "        if node.left and self._isRed(node.left.left):\n",
    "            node = self._rotateRight(node)\n",
    "            self._colorFlip(node)\n",
    "        return node\n",
    "    \n",
    "    def delete(self, obj):\n",
    "        \"\"\"Public function for deleting node containing obj.\"\"\"\n",
    "        if self.tree == None:\n",
    "            return\n",
    "        else:\n",
    "            self.tree = self._delete_node(self.tree, obj)\n",
    "    \n",
    "    def fixUp(self, node):\n",
    "        \"\"\"Rotates and colorflips where necessary. Used internally to preserve RBT properties.\"\"\"\n",
    "        if self._isRed(node.right): \n",
    "            node = self._rotateLeft(node)\n",
    "        if self._isRed(node.left) and self._isRed(node.left.left): \n",
    "            node = self._rotateRight(node)\n",
    "        if self._isRed(node.left) and self._isRed(node.right): \n",
    "            self._colorFlip(node)\n",
    "        return node\n",
    "        \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### **4. Demonstrating red/black trees**\n",
    "In this section, we demonstrate the use of the red/black trees implemented above, providing some visual comparisons with ordinary binary search trees. An example of worst-case insert for an ordinary binary search tree is considered."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['Alice', 'Bob', 'Carol', 'Doug', 'Eve', 'Frank', 'Ginger', 'Howard', 'Irene', 'Jeff', 'Kathy', 'Luis', 'Mabel', 'Norm', 'Oprah', 'Peter', 'Queen', 'Ronald', 'Sarah', 'Tom', 'Ursala', 'Vince', 'Wanda', 'Yaakov', 'Zandra']\n",
      "['Alice', 'Bob', 'Carol', 'Doug', 'Eve', 'Frank', 'Ginger', 'Howard', 'Irene', 'Jeff', 'Kathy', 'Luis', 'Mabel', 'Norm', 'Oprah', 'Peter', 'Queen', 'Ronald', 'Sarah', 'Tom', 'Ursala', 'Vince', 'Wanda', 'Yaakov', 'Zandra']\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAxsAAADnCAYAAAB2Zks2AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAAgAElEQVR4nO3dd7xcVbn/8c+XhJCEAKGDtNA7hIQivSuooCAIiBRBAaMIoperXi7iT4FrwQZEbFSV3gMiSK8mENJASKQpHQIBAiGkPL8/1hrP5DDn5JSZ2TNzvu/XK6/M2bP3nmfP3jnZz17PWksRgZmZmZmZWbUtUnQAZmZmZmbWmpxsmJmZmZlZTTjZMDMzMzOzmnCyYWZmZmZmNeFkw8zMzMzMasLJhpmZmZmZ1YSTDTMzMzMzqwknG2bWY5LmSZogaaKk8ZK2W8j6u0gaU6/4zMzMrFj9iw7AzJrarIgYDiDp48CZwM7FhmRmZmaNwi0bZlYtSwJvAij5iaQpkiZLOqh8PUk3SXpS0nmS/HvIzMysRbllw8x6Y5CkCcBAYGVgt7x8f2A4sDmwHDBO0j35va2BjYDngFvyulfVM2gzMzOrDz9RNLPemBURwyNiA2Av4GJJAnYALo2IeRHxCnA3sFXeZmxEPB0R84BL87pmZmbWgpxsmFlVRMSDpFaM5Re26kJ+NjMzsxbhZMPMqkLSBkA/YDpwL3CQpH6Slgd2AsbmVbeWtGbuq3EQcF8hAZuZmVnNuc+GmfVGqc/GIqTfJz8AdgcWAxYF3gZmAVeQyqhWA6YAvwHWAO4Erq1/2GZmZlYPinAFg5klubVhKWDZ/Ge5Lr4e0IOPm08avWo68Hr+e2Gv34iIOT07OjMzM6s3JxtmLUpSf2Bpup4wLAssQyqFqmQe8AZdTwymk5KJwd2MYTnS6FYdebubMUyPiFkL+brMzMysBpxsmDUBSYvR/daGoZ3s8gPabsa7euP+dkTMr/KhVSRpMN0/3iU62eV7dCM5ya9nhn9BmpmZ9YqTDbM6ysPCdvdJ/7LAkE52+y7dfNIPvNtqN9KSBpBaZrrz3S4NqINdzqF7ycl0YEa9EjIzM7Nm4GTDrIdy4lDq39CdG9zFOtntDLrfh+H9Kh9anyGpHynh6G4rSkelZvNJpWbdSfzcD8XMzFqWkw0z/nPTuQzdu+lcloXfdC7sZrP9Tefc6h+dVVNOMpek+0lmZ/1Q3qKbrShOMs3MrBk42bCWk8tpunsjOJSOy2k+oPv1/m+5nMbK5X4oHXWI7+ja7Kx87j26Xz7nfihmZlZXTjasYZX1b+huiYtv0Kwl5IEBetIPpSNOnM3MrK6cbFhdlJWedLdjtEtPzLqhbMjjepcElr92SaCZmQFONqwH2nWq7WrysAwdz1jvTrVmBarxYAdd/TfthwFmZi3IyUYft5DhQju60fBwoWZ9XA2Hce7u74+WG8bZzKyVONloIZ4IzcwaXY0nqOzq7yr3QzEzqxMnGw0oPzFcgu4/MRzUyW7fppv/IUfErCofmplZt5X1Q+nO78Rl6LgfyjzaSje7Ojz1m+6HYmbWfU42aiz3bxhK92uhO+rfEHT9P8nSa/dvMLM+RdIitPVD6c7v3wGd7PZNut8PZXaVD83MrKk42egGSYuy4OgtXfnPaxk67t8wl+43/8+IiHnVPzozs74ttyovTvcfDi3eyW5n0v1+KO+5HNXMWkWfTTYkDaL7/6Es2ckuZ9H9/1De8X8oZmbNTdJAuv8gqrN+KLPpWT8U/39iZg2n6ZONsv4N3W0qX1j/hu42lb9X5UMzM7MWlfuhLEP3hxBfpINdzqX7JbZvuqXczGqtIZINSZ8BrgU2jIgnJA0DxkTEJpK2BI4ijdne0S/hRTvYdZBqbLs7GdUH1T9KMzOznivrh9LdwUM66ocSpP9bK/1feHlEjK3VsZhZ39EoycblwEeAOyLie+XJRn5/AG3jr3c0Ukil1+7fYGZmfVZu/X8H2ISUeKwN/C/wPDCWjhOVURFxURExm1lr6ag5tm4kDQF2AI4GDq7w/i7ANaQnM+uQfjkunV/fEhHfASYBxwDfB74BvBAR051omJlZX1bqxxERz0bEIxFxBfBpYGvgNOBbwPvASqTBTI6MiMVJeco5pf1IGpP/P0bS0ZKmShor6Xfl65mZtVd4skH6pXdLREwFpksaWWml/Avzf0md4DaNiM2AOyQtB5wC7BERI4CHgZPqFLuZmVlTiYinSXOQrAB8NS2KTYFDgItyh/eKJH2E9H/xR4HtgQ1qH7GZNbNGSDYOAS7Lry/LP3dkD+Dc0g8R8SbpF95GwP2SJgBHAGvUJlQzM7OWsgPwR4CIeAJ4Dlivk/W3Bu6OiNL8TVfWPkQza2YdTRxXF5KWAXYDNpUUpCctQVlC0ZXdALdFRGdJipmZmQGS1iLNov5qJ6vNZcEHkh22dpiZdabolo0DgEsiYo2IGBYRqwHPAKt1sP5tpCZfACQtDTwEbC9pnbxscUmdPZUxMzPrkyQtD5wHnJPLk+8FDs3vrQesDjwJPAsMl7SIpNVILRoA44CdJS2dh+/9bJ0PwcyaTNHJxiGkIW/LXQ18p4P1fwgsLWmKpInArhHxGnAkcKmkScCDuIbUzMysZJCkCZIeA/4G3EoaUAVgNLCIpMnA5aQO4rOB+0kP/x4HfgWMB4iIF4AzSIO13E9KSt6q36GYWbNpiKFvzczMrP5yOfN6wPr5z0bAJ4AppFaPJ/OfqcDzERGShkTEzNyycS1wfkS0f3BoZgY42TAzM2tpkhYjza9RnlSUXi9XtupcUgfxgcAsYGVg8bL33yMlHYOAocB84B7gmIh4u7ZHYWbNysmGmZlZk8uT932EBROJ0us1WbBs+hUWbLEovX4mjzBVaZ/t9zus3T5frrC/qe33aWZ9j5MNMzOzJiFpCdpu+tsnFeWtELP48I3/k8DUiOh1H4uy1pJKcbRvLXm6QhxPAq+Gb0LMWp6TDTMzswaS+0IMo3KLwsplqwapg3alFoUXImJ+3YIuk/uBVEpC1gUWK1v1LcqSINrinxYR79UzZjOrHScbZmZmdZZLlJancj+KtYFFy1Z/g8otA09FxPt1DLtXJPUjDa1b6ZjbD3n/byonUf+KiHn1itnMes/JhpmZWY1IGkR6ol/pBnto2aofAP+kQlIREdPrGXMRJA0mfU/tW0TWB5YsW3U2MI0KJWIR8UY9YzazrnGyYWZm1guSFiE9ma9UOrQ6oLLVn6dyX4rn/MT+w3IL0ApU/m7XBvqXrf46lb/bp/LcIWZWACcbZmZmXSBpKJX7UaxLGi625B0qlwBNi4iZ9Yy5lUlalDTSVqVWo5XKVp1PW9+W9uflRXdSN6stJxtmZmaZpAHAWlROKpYvW3UebaMstU8qXvYNbLEkLUVbWVb5eVwPGFy26rtU7qQ+NSLeqWfMZq3KyYaZmfUpuTRnZSo/EV8T6Fe2+itULs152vNHNJ9c8tbZ3CHlJW8v0fHcIXPrF7VZc3OyYWZmLUnSENLNZPukYj1gibJVS3NStL+pnBoRM+oZsxVH0kA6njtk2bJV5wBPUTkJfc2tWmYLcrJhZmZNKw+nOozKN4irlK0awHNUflL9fFFzUlhzkLQsHc8dMqBs1RlUTkKmRcSsesZs1iicbJiZWUPLZU+lm732N3xrs+DN3pt0PCeFb/asqsrmDql0ba7abvV/Ufna/LeTXWtlTjbMzKwh5DKWdah847Z02apz6GBOCmC6y1isEUhanI7nDikv43ufNHdIpU7qb9YzZrNacLJhZmZ1kzvorkrlztlrsGAH3RfoeE4Kd9C1ppRb6lak47lDygcoeI3KpX9PRcQHdQzbrMecbJiZWdXloUc7mpNiUNmqM6l8MzXVc1JYX5PnDlmLysn4imWrzgOeoXIy/pJb96yRONkwM7MeKbsxqpRUrFC2aunGqFLZk+ekMOuCPKlkR3OHtE/gKyUhTuCtEE42zMwMAEkrAb8AtiKNqvMKcGJETG233qrAHaREo7zk41Uq3+TcAmwZEa/X+hjM+gpJMyNiSC5N/AJwBnAeafLJUhIyjAVLE18HRkXElZIuBMZExFV1Ddz6nP5FB2BmZsXLdeTXAhdFxMF52eak0o2p7VZ/FZgAXEFbUjEtIt7oYN+1CtvMYFfgVGDniHiq/I2yQRfWA0YBS5H6QpnVzSJFB2BmZg1hV2BORJxXWhARE4FHJd0uabykyZI+nTumngwcCOwJnA8sIemQvM4UST8q5CjM+hBJOwG/Az5VSjQk7SPp75IeBcaQOpmPBzYhzZ4+WtKOeRc7SXpA0tOSDsjbXyzpM2Wf8SdJn67jYVmLcRmVmZkh6evAmhHxjXbL+wODI+JtScsBD5HqxtcAnga2i4iHJH0kvzeSNNfFrcCvIuI6Sc/iMiqzqpI0B3gH2CUiJpUtXxqYEREh6UvAhhHxTUmnATMj4qd5vQuBxYGDgA2AGyJiHUk7A9+IiM/kgR4mAOt6BDjrKbdsmJlZZwScIWkS8DfSrNylUXGei4iH8uutgLsi4rV8U/InYKe6R2vWd8wBHgCObrd8VeCvkiYD/wVs3Mk+rouI+RHxOPnfdUTcDawraXngEOBqJxrWG042zMwM4DFSq0R7h5I6nI6MiOGkTuMD83vv1ik2M/uw+cDngK0lfbds+dnAORGxKXAsbf9eK5ld9rq8c9XFpE7nXySVSZr1mJMNMzODNLrUYpKOKS2QtBmpXOrViJgjadf8cyVjgZ0lLSepH+mJ6N21DtqsL4uI94BPAodKKrVwlHcCP6Js9XdYcObyzlwInJg/4/HeR2p9mZMNMzMjz3WxH7CHpKckPQacCdwMbJlLMg4Hnuhg+5eAbwN3AhOBRyLi+roEb9aH5VHg9gJOkbQvcBpwpaRHSEPdltwIHJkHcdjxw3taYJ+vAP8ALqhN1NaXuIO4mZmZWQvKE2/uCOxDepiwBmnSv2tJycdfI+LtCtsNBiYDIyLirfpFbK3IyYaZmZlZi8ijUe1NSjD2JpVVzSaVNf4LWJo01PUypE7md5ESjxsj4llJewB/AH4eEb+o+wFYy3GyYWZmZtbEJK1LSi72IbVk9CPNrzGGlEjcFhEzy9bvD2wL7Ju3WT+/NTmvfwMwLiLm1+sYrHU52TAzMzNrInkQhvJkYYP81hRyKwUwNiLmdXF/69GWrOxASlZeAW4iJR5/iwiPPmc94mTDzMzMrMFJWhL4GCnB+ASwLDCXBcugnqnC5yzDgmVYS5LKsG4nJR5jIuKFjvdgtiAnG2ZmZmYNSNIapJv+fYFdgEWBN0ktDqUO3jXrwC1pAG0dzPcF1sxvjSclHjcCj4ZvJq0TTjbMzMzMGoCkRYCtaLu53zS/NZW2m/sHipjRW5KAjWgrt9qWNBHgC7SVbt0REe/XOzZrbE42zMzMzAoiaXFgD1Jy8UlgRWAecB9t5VFTi4uwMkkrkMq59gE+DiwOvAfcRkqMbsrzdVgf52TDzMzMrI4krQJ8ipRg7A4sBrwN/IWUYPwlT9bXFCQNJJV5lVpkVgUCGEtbi8wUl1v1TU42zMzMzGoolyBtQdvN+Ij81jO03YzfGxEfFBNh9eRj3Zy2Y90yv/UsbeVWd7fCsVrXONkwMzMzq7L8tH832vo4rEJ62v8QbQnG463+tF/SR0jlYfuSysUGAu8At5C+g5sjYnpxEVqtOdkwMzMzqwJJK5JurPchDVM7GHgXuJWUYNwcEa8WF2GxJA0mlY3tSyojWwmYD9xPW6vHk62egPU1TjbMzMzMeiCXDG1CW+vFNqQRmp6nbSbuuzxC04flkbdG0jYx4eb5rWm0JR73FTHyllWXkw0zMzOzLspzT+xMW4IxLL/1MG0JxkQ/ne8eSavT1ml+V2AAaU6RUqf5WyJiRnERWk852TAzMzPrhKRlaRvmdS9gCeB94G+kG+ExEfFicRG2FklLAHvSNhzwcqTZ0u+hbTjgp4qL0LrDyYaZmZlZO5LWp63EZ3tgEeBlYAyp9eL2iHivuAj7Bkn9SOVppXOxUX7rcdrKrR6KiHnFRGgL42TDzMzM+jxJ/YEdaCuPWje/NZG2m9qHI2J+MREagKS1aTtHOwH9gdeBm0jn6NaIeKe4CK09JxtmZmbWJ0kaSiqL2gfYG1ga+AC4k7byqOeKi9A60+78fQIYyoLn78aI+FdxERo42TAzM7MWImlmRAzp4rpXAAfiJ+MNS9KqwLmk8ql+wM3ANyNidrv1FiWVu5UmE1wHeBVY2a1RxXKyYWZmZi2jUrIhqX+lIVQljSRNMuea/waUhxb+O/DriLgg99/4LTAzIk5YyHbrA2tGxF/qE611ZJGiAzAzMzOrNkm7SLpX0g2kzsRI+oKksZImSPoNMCEi7gfeknS6pImSHsqT8yFpeUlXSxqX/2xf4CH1RbsB70fEBQA5IfwGcLikr0k6p7SipDGSdsk/7glcAJwu6UpJQ/I6IyXdLekRSX+VtHJefpekH+VrY6qkHet4jC3PyYaZmZm1qhHACRGxnqQNgYOA7SNiODAPODSvtzipdWNz0vCqX87Lfwn8PCK2Aj4L/L6u0dvGwCPlCyLibeBZUsfwD5G0HHAKsEdEjCDNf3JSLrM6GzggIkYC5wOnl23aPyK2Bk4Evlfl4+jTKp4oMzMzsxYwNiKeya93J81YPS5V2TCIVNMPqVPxmPz6EdKTcYA9gI3y+gBLShoSETNrHbj12EdJ/Tvuz+dtAPAgqaxqE+C2vLwf8FLZdtfkvx+hbaJGqwInG2ZmZtaq3i17LeCiiPhOhfXmlM34PY+2+6NFgI9GxPs1jNE69jhwQPkCSUsCKwHTgfXK3hpYWgW4LSIOabfdpsBjEbFtB59V6nBefv6tClxGZWZmZn3B7cABklYAkLSMpDUWss2twPGlHyQNr2F89mG3A4MlHQ7/meDvLOAc4BlguKRFJK0GbJ23eQjYXtI6eZvFJa0HPAksL2nbvHxRSRvX93D6JicbZmZm1vIi4nFSLf+tkiYBt5Fq+S/rZLOvA1tKmiTpceC4OoRqWW5t2o+UJE4jtWbMj4jTgftJCcfjwK+A8Xmb14AjgTslvUkqodogIj4gtZL8SNJEYAKwXX2PqG/y0LdmZmbWp0haCfgJ8IW8aBzwlYh4pOOtrGiStgMuBfaLiPEdrLMy8FPg83nR30nn9tH6RGntuWXDzMzM+gRJ/SUdTyqp+RxpNKKjgNVJHcfPlbR0kTFaxyLigYhYo1Kikc/tCcATpBaMHwBfAtYEHpZ0dp5x3OrMLRtmZmbW8nKt/mhgOKmE6msRMTW/txTwfVL/jOnAycDFnnm6OeT5T0YDmwG3AMdHxD/ze0NJicco0kzx/wVcEr4Brhu3bJiZmVnLyhPz/QF4AFgOOBD4eCnRAIiItyLiRNK8HNNIE8LdI2nzImK2rpG0gqQLgfuApYH9gU+UEg2AiJgREccDWwFPAxeRzu2mBYTcJznZMDMzs5YjqZ+kY0klU4cDPwY2jIirOnqqHRETgR2BL5KGVR0v6Re55cMaRD63o0jn9vPA/5HO7bWdnNvxwPak0qoNgUcl/SwPpWs15DIqMzMzaymStiKV1WwJ3AV8NY9G1Z19LE3q03Ec8ArwLeDPLr8plqRtSOd2BHAH6dw+0c19LAucQZop/mXgJOByn9vacMuGmZmZtYQ8d8Z5pBGIViE99d6tu4kGQES8GRGjSOU3/wL+SBpO1XMzFEDSspJ+SxrKdiXgYGCP7iYaABExPSKOJc02/iJphKu/SdqwmjFb4mTDzMzMmlqe2O0oUlnNl4BfkOZWuLS3T6vzcLjbAscCmwITJP1E0hK9jdsWLp/bLwNTSSOH/Yx0bnvdEhERY4FtgK8AWwCTJP1I0pDexm1tXEZlZmZmTSvP6j2alBDcRyqrmVSjz1oOOJOU0LxAKr+50uU3tSFpBOncbgPcQzq3U2r0WcuT+n4cBTwPnAhc43Pbe27ZMDMzs6YjaaikXwGPAGsDRwA71SrRAIiI1yPiy6TE5lXgctKM5OvX6jP7IklLSzoXeBgYBhwG7FKrRAPSzOMRcTSpE/l04CrgFknr1uoz+wonG2ZmZtY0lBxGmrztq8CvgfUj4uJ6PYWOiIdIfTm+lv+eLOkMSYvX4/NbVT63R5DK4Y4DziaVTP2xjuf2AdLAAieQ+nRMkfQDSYPr8fmtyGVUZmZm1hQkbQKcC+xE6gQ+qtJs0nWOaQXSsLpHkDqSnwBc7/Kb7pG0Genc7kDqBD4qIiYUHNNKwE+ALwDPAidExA1FxtSM3LJhZmZmDU3SEpLOAiYAG5P6TGxXdKIBEBGvRsSRpAToLeBa4CZJaxcaWJOQtKSknwPjgQ1IfSZ2KDrRAIiIlyPiMGBn4F3gekk3Slqr4NCaipMNMzMza0i5rOZgUsnUN4A/kEqm/hAR84uNbkERcS9p7odvkJ7OPybp+5IGFRtZY8rn9vOkkqkTgN+Rzu0FDXhu7yGNVvUtYBfSuT1V0sBCA2sSLqMyMzOzhiNpA1JZzW6kTuCj8lClDU/SR4CfAocATwNfj4ibio2qcUjaiHRudwHGkc7tw4UG1UWSVgHOAg4CngKOj4i/FBtVY3PLhpmZmTUMSYtLOhOYRGopGAVs0yyJBkBEvBgRnyclSrOBMZKukzSs0MAKJmmIpB8DE4HNSXOXbNssiQZARLwQEQcDewJzgZslXSNp9YJDa1hu2TAzM7PCSRKwH2lCvtWAC4D/jojXCg2slyQNIM3ZcCrpIe/pwE8jYnahgdVRPrcHAD8nzez+B+DbEfF6oYH1Uj63JwH/Cwj4AXBWRHxQaGANxsmGmZmZ1ZykecDkskWXRcT/5ffWAc4BPk5q0RgVEffXP8rqkjQzIobk16uRZr8+AJhGGjZ3A9Ls1eNJHaNvApYDzoyIywsJugvKzmV/4B/AERHxXgfrrkc6rnWAR0nn9qF6xVotkpYFbs8/rgTMA0qJ8GdJo1btR+qD8rWI+Fvdg2xQ/YsOwMzMzPqEWRExvIP3hpMmyjsBGB0Rc+sXVn1ExL+BAyV9jJRY7U/qs7BHRDwv6aN5vY6+o0byn3Mp6U+kOTF+1sG6I0iJxvHAryNiXlc+QFK/rq5bDxExnXSdIuk0YGZE/LRslf0l7U2aG+QzgJONzH02zMzMrBCS9pJ0JXA1aRbwScB1+b2PSXpQ0nhJV0oaUmSsvSHpvySNkzSJNEP1psCiwFrAXyT9N/BHYCtJE5ps2Nx7SckEkr4gaWw+ht9I6ke6QZ9PGq744k7WQ9JMSWdJmkhKPpuCpJMlTSG1bpwLfFvSOpKmSLpE0lRJF0v6uKQHJE2TtGXBYdeNkw0zMzOrh0H55rL05yDS099tgMG5fv8g4DJJywGnkJ76jwAeJtXGN53ckrEusDXpxnskqcP70cCLwK4R8SPSzfi9ETE8Ip4qLOBukNQf2Js0g/qGpPO3fW71mAccGhHfJreERMShHa2Xd7k48PeI2Dwi7qv7AfWApG1I8W9FSpCOAdbMb68PnEkql9sM+GxEbAd8O//pE1xGZWZmZvVQsYxK0i3APpKuAj4JnEyaRG0j4P7Ut5gBpFmlm9HH8p9H889DSMnHPYVF1HuDJJUm3buX1OH7GFIiNS6fs0HAqxW23b2T9eaRWrmayQ7A1RExC0DSdcCOwK3APyPi8bz8cdr6fEwGvlNArIVwsmFmZmZFuozUWfoN4OGIeCePXnRbRBxSbGhVIVKH798UHUgVfShxzOfsoohY2E10Z+u930j9NKqgfMSx+WU/z6cP3YO7jMrMzMyKdDepE/GXSYkHwEPA9nmUqtLcG+sVFF9v/RU4qtTnRNIqklYoOKZauB04oHRskpaRtEZ+b46kRbuwXjO6F9hP0qB8jj+dl1nWZ7IqMzMzK1R56Q3ALRHx7YiYJ2kMcCRwBEBEvCbpSOBSSYvl9U8BptYz4N7I/RlmR8StuZ/Cg7lsaCbwBSqXGDWtiHhc0inArZIWAeYAXwWeA34PTJI0Pvfb6Gi9phMRYyVdSpoJHeB3wBTSgAeG59kwMzOzgkn6BPBLUmfp54uOpxokbQ78LiK2LjqWIknagzRC0yeapeN7T0laEngGGB8RexYdT6NwGZWZmZkV7V+kidKukzS46GB6S9JxwKWk1pg+S9K6wJXAB7RYS04HzgSWAfaQtF/RwTQKt2yYmZlZ4STtA1xPujk9OHyD0tQkDSX1vVkW2Doinik4pJqSNIrUgnMWaTSqjUnD+04sNLAG4GTDzMzMGoKkk4EfAadGxA+Kjsd6JvdXGQPsRporpZmH+V0oSbuRhrr9C2n28BVIfTjmAVtFRF9o1emQkw0zMzNrCKXhU4HDSBOgXVNwSNYDkn4OnAh8KSL+UHQ8tZRHTBtLmqBxu4h4Oy8fSRqVajywe0TM7ngvrc3JhpmZmTUMSQOBO0kzLm8fERMWsok1EElfIo3I9MuIOLHoeGpJ0lKkUrHlSaViT7d7/3PA5cAFwNF9tTTQyYaZmZk1FEkrkcpQglSG8krBIVkXSNqRNI/GncAnI2JuwSHVjKR+pFKxPYA9I+KuDtb7PnAq8M2I+Fn9ImwcTjbMzMys4UgaAdwHTCANidtny1CagaRhpATxDWCbiJhRaEA1JumnwDeBYyPit52stwhwBbAf8KmI+EudQmwYTjbMzMysIUk6kHSjdjFwZF8tQ2l0kpYA7gdWIyUaTTP5Yk9I+iJwPnB2RHy9C+svTkqc1wI+GhH/qHGIDcXzbJiZmVlDiogrgdOAw0lPka3B5Cf3fwQ2Aj7XBxKN7YHfAH8DTurKNhHxLvBpYBZwo6Rlaxdh43HLhpmZmTWsfDN7GXAAsE9E3FRwSFZG0hnAd4DjI+KcouOpJUlrkErFZpBacN7s5vbbAneRWjn2iog5VQ+yATnZMDMzs4aWZxW/F1gX2DYiHis4JAMkHUpq1fgN8JVWLnOTNIRUKrYGKdF4sof7OZw0vPPoiPhqFUNsWE42zMzMrOFJWpX0VPk90jCj0wsOqU+TtA1wN/Ag8LFWfkqfW9euBvYF9o6IW3u5vx8BJwNfjYjRVQixoTnZMDMzs6Yg6aOkMpSWv8FtZGWJ3ynSbpYAABmLSURBVCxS4vd6wSHVlKQfAv8DnBgRv6zC/voB1wN7ka7jO3q7z0bmZMPMzMyahqTDSKNTtXzpTiMqK2lbjzSyUkuXtEn6PPAn4PfAMdW63iQtSUqaVyYlbP+sxn4bkUejMjMzs6YREZcAPwKOBUYVHE6fIknAhcAWwCF9INHYmjTE7b2kkqeqJbYR8TawDzCfNELVUtXad6Nxy4aZmZk1lVyGci3wCdKoPn8rOKQ+QdKpwPeBkyPiJ0XHU0uSViGVis0mtTy8VqPP2QW4jTSU7qciYl4tPqdITjbMzMys6eSJ5B4AViXdDE4rOKSWJukA4Er6wASLuVTsbmADYLuImFzjzzuGVBb4s4houflkXEZlZmZmDUPSPEkTyv4Mq7ReRLxDGh1oHqkMZehC9nuXpC2rHnALkDRzIe9vQUoyHiRNsnhlHcLqlbLraIqkhV4fZdsJ+AMwEji0s0RD0oU5CSv9/HNJJ0raRdIYSX+V9Puy98+S9KGJACPit8DZwEmSjlpIfMMkTenKsTQKJxtmZmbWSGZFxPCyP8+Wvympf+l1RDwD7A88CnhkqtqZQRoFbP+IeCYiDljI+o2gdB1tArwBdGdOi4nAtyPihm5+5v3AdmU/LwdsXPbzdqTWuEpOAq4AnuvmZzY8JxtmZmbW0CQdKekGSXcAt0saIul2SeOBc4HLIuLd/NT3H5J+J+kxSbdKGtRuX4vkJ9I/LORgmkT5U/uc1O0UES+XP1mXtLGksbkFYZKkdQsNumMPAqtAarmQ9JPc4jFZ0kF5+S6S7iK12hwJbJ5bOZB0qqRxeZvflpaXk7QX8H/AZ0gJ8BLAFOAdSUtLWgzYEHi8dO3mz/903sWqwGbAwe2vXUkjJU2UNJGypCmfi3vzvsZLKk90GoaTDTMzM2skg8pKqK4tWz4COCAidgbeB/aLiBHArsBZZTeA6wLnRsTGpCfyny3bR3/SMKbTIuKUmh9J6zsO+GVEDAe2BJ4vOJ4PyYMJ7A6UWin2B4YDmwN7AD+RtHJ+bwvgRGAjYC1g+7z8nIjYKreSDAI+1e4zBgK/A/YGXsjbLk1Kcv4ObEv6fiaTJqXs7rV7AXB8RGze7vBeBfbM+zoI+FW3v6A66L/wVczMzMzqZla+eW3vtoh4I78WcIaknUhDh64CrJjfeyYiJuTXjwDDyvbxG+CKiDi9+mH3SQ8C/5Mn+bumwTrpD5I0gXRt/IM04hPADsCledSnVyTdDWwFvA2MjYjnAfK2w4D7gF0lnQwMBpYBHgNuLPusDUjX3TRJDwAvkpKZUovKdsBbpDKrbl27ua/J0Ii4Jy+/hJTUACwKnCNpOKnv0nq9+L5qxi0bZmZm1gzeLXt9KLA8MDInJq8AA/N7s8vWm8eCD1YfIN04DsQWZi75PlHSIsCA9itExJ9JnfRnATdL2q2uEXaulLSuQbrB70qfjQ9dO/laGU1qVduU1ILR2fVzPyn5WJJURvUQqWWj1F+jp9duJd/I229Oajn50DlqBE42zMzMrNksBbwaEXMk7Uq6oeyKPwA3A1eUdzS3ip4ljcgEKaFYtP0KktYCno6IXwHXk/ocNJSIeA/4OvDNfM7vBQ6S1E/S8sBOwNhOdlFKBF6XNASo1Dn+CVIrxNrkhBb4ICLm5da4oaSE4wG6ee1GxAxghqQd8qJDy95eCngpIuYDhwH9OttXUfwPzczMzJrNn0jD3U4mlZs809UNI+JnSrM1XyLp0Hyj1tcNllTe3+JnpCf41+dOybcAs3ILR7nPAYdJmgO8DJxRl2i7KSIelTQJOAT4I+nGfyIQpAkKX5a0QWn9fH0MzdvOkPQ7UivFy6SJ/trv/32luTJuIvXJWBR4qWyVycCQiHhdUvm1+zApUSlZQtJKEfFyu4/4InC+pABuLVs+Grha0uGkc/QuDciT+pmZmVnTkvQT4GvAKmV9OqyKJO1Larn4WETctrD1m13ur/FOROxYx89cn5R43B8ROyxs/WbiMiozMzNrZn8klbocWXAcreyvwOvAqKIDqZNLgB0kbVrHz9wn/72+pA+VrDUzJxtmZmbWtCJiIqlT7nEVynysCiJiNvB7YN888lSru5A0vPJX6vFh+bo9jlSqtRxpro6W4X+UZmZm1uxGk+Yo2L3oQFrYb0ijOh1TdCC1FhHTgctJ/VGWrMNH7gmsDZxJ6phflySnXpxsmJmZWbO7GniNvlPmU3cR8SxpJK8vS2rIIVarbDQwBPhCHT5rFGmCvquB80jDM29Yh8+tCycbZmZm1tTalfmsVnQ8LWw0sBItVubTgXGkkc5Glc3wXXWS1iDNSP77fB2fD3xAC7VuONkwMzOzVtBnynwK9FfSMMMt34IUabjW0cDGQC1HpSpdr7/Nn/sacAVwRJ7Xo+k52TAzM7OmFxHPAWPoO2U+dRcR80hlPjtL2rjoeOrgMmAGNUquJC0GfAkYk6/fktGkGcg/X4vPrTcnG2ZmZtYqfg2sCOxXdCAt7HxgNi1U5tORPPv4BcBnJa1Ug4/YH1iBlFyUewiYAHy1liVc9eJkw8zMzFpFnynzKUpEvE4q8zlc0hJFx1MH5wH9SS0Q1TYKeApYYKLEshKuzUiznTc1JxtmZmbWEiJiPql1YydJmxQdTwsbDSwBHFp0ILUWEVNJycCxkvpXa795wsAdgF/n67a9PwNv0wKJs5MNMzMzayUXkMp8jis6kBb2d+BR4CutUObTBaOBVYFPVnGfXyFNHHhhpTcj4t383oGSVqji59adkw0zMzNrGbnM53L6TplP3bUr89mu4HDqYQzwPFVqZcgTBR4GXJYnEOzIr4EBwFHV+NyiONkwMzOzVtNnynwKdCnwFi1Q5rMwETGXNLTyxyStW4VdfoE0YWD7juHtP/cJ4A7gOEn9qvC5hXCyYWZmZq1mLDCeGk/I1pe1UplPF/0emEsvy/Py9TgKeDgixnVhk9HAGsDevfncIjnZMDMzs5ZSVuazKbB9weG0svOARYGjiw6k1iLiZeAa4IuSBvdiVzuSJgr8dRfXvwF4iSZuQXKyYWZmZq2oz5T5FKVVyny6YTSwNHBQL/YxijRR4GVdWTki5pBmF99L0tq9+NzCONkwMzOzllM2IdsBklYsOp4WNhpYHfhE0YHUwT3A4/Qwgc0TA34WuCBfn131O2A+cGxPPrdoTjbMzMysoUlaUdKfJT0t6RFJD0raT9KWkn7VyaZ9psynWiSFpD+W/dxf0muSxnSwyQ3Ai8Dpks7p5mc9K2m5XoRbFZL+R9JjkiZJmiBpm0rrlZXnbSnpqXb7OE3Styr9rOQ+4EekCQLPk3SgpFva7WOYpCkVPvcF4DrgaEnPSxray0Ouq6pNTmJmZmZWbblD7XXARRHx+bxsDWDfiLgWeLijbSPiSUmH0m6G5m5+fv88GlFf8S6wiaRBETEL2BN4oaOVI2KOpKOBLYBV6hRj1UjaFvgUMCIiZufkZ0Anm1wC9CNP8reQa2MRSEmKpONIfT6OJCVnNwF7dSPUHwBnA3/qxjYNwS0bZmZm1sh2Az6IiPNKCyLiuYg4W9IupSfu+Uny+ZLuyi0gX8/r/pnUp+BJSfdJurTsifPakm7JrSX3StogL79Q0nmS/g78uO5HXLybaZvA7hBS/xcAJG2dW5YelfSApPUj4hZSJ+bV8vc/TdL3yrb5gqSxudXgNw3Wv2Nl4PWImA1pnpaIeFHSqZLGSZoi6bdlo5rdAAwH1gJOkLRPvk6OBY6RdL+kXwDHkEr4HpP0AfBXYBAwDPgpqcXtSkkzJD0h6THK+oLklrx3JM2S9CKweETcXfb+YEm3Sjoq/3xyjnWKpOPzsp9KOrZsmx9KOrEWX2JnnGyYmZlZI9uYNIxtV2wAfBzYGviepEUlbUWqk9+cNHzolmXr/xY4PiJGAt9iwXkPVgW2i4iTehl/M7oMOFjSQNLEfX8ve+8JYMeI2AI4FTij7L2tSd/1ZqQhcbeUtCHpJnr7iBgOzKOx5j+5lZQkTZU0WtLOefk5EbFVRGxCShI+VbbNosBTEXEWcB/wUdI8HBNI/VcGkK6tuUAAI4CBpJHRPg/sAGwWESOAPYCZwFbAl2i7N/8vYHnSfDEv5P2VLEGaaPDCiDg/l30dmvexLWnI501Jk1t+rmy7A4ErevpF9ZTLqMzMzKxpSDqXdLP2AemGrNxN+Qn1bEmvAiuSbvCuj4j3gfcl3Zj3M4Q0+/WVbQ+tWaxsX1dGxLzaHUnjiohJkoaRWjVubvf2UsBFSpPbBenGu+S20ozYkq4hnae5wEhgXP6eBwGv1jL+7oiImZJGkoak3RW4XNK3gXcknQwMBpYBHgNuzJvdSCobg5SUXk5KZkW6t7487+smYDXg56Trdcn83lzgXEnDSQnFCsCDwErAK3m/BwPfzZ+/KClJKxkDnBERl+efdwCuzmVvSLqOlBCOlrSa0gAJqwIvR8SLvfvGus8tG2ZmZtbIHiM9GQYgIr4K7E66SWtvdtnreXT+UHURYEZEDC/7s2HZ++/2IuZWcAOp3OfSdst/ANyZn/jvQ3piXxLt1g3SDfhFZd/x+hFxWo1i7pGImBcRd0XE94CvkVoJRgMHRMSmpNGgyo/zJdIQuJD6UZxDSiL+QLquStfO7Ig4DjiF1M/jFlJCuwMpqTgJeBKYHxGbk1qNFsmJ3HeBPwOL532XX8v3A3uXlXZ15ipSa9NBeT9152TDzMzMGtkdwEBJXylb1p1J1e4H9pE0MLdmfAogIt4GnpF0IPxnxKDNqxV0Czgf+H5ETG63fCnaOowf2e69PSUtI2kQ8BnSd387qe/CCgD5/TVqF3b3SFo/39yXDCclAACv52vmgHabzQJekrQb6ft4h9TZe9126yFp7Yj4O6k1Z3pefyApYVkSGAL0k7QxqfyMvHwu8BypdW4fFrxn/y7wHlAaie1eYD9Jg3K8n87LICUYB5MSjqu68p1Um5MNMzMza1h5uNHPADtLekbSWOAi4L+7sPkQYGfSiFWTgL8Ak0mT/UF6gn20pImkFpRPVzn8phURz0dEpWGFfwycKelR8tP23El5K2AscDXpu746Ih6OiMdJT/ZvlTSJNDLYyvU4hi4aQioLezzHtxFwGqk1YwqpY/e4CtsdDvwvKXm4hVTq9EyF9X4iaTKwDvAvUr+iB4AjgO+RWkgC+CGpzwekPkoPAqcDU4GXgTmSyvsPfRUYKumMiBhLaoEaBzwE/LqUJEbERFIr4NMRUUj5mtK/YTMzM7PWImkw8Dbw04j4dv75HuCYiOhqp3NbiJwAvhcRuxQdSyOT9DVS2dXqEfHvbm57FmkywSXzrOJNwy0bZmZm1pLyLM2PAYdLmkB6Yny1E42qGweMbLAhbRtRqYVkqx5uOxDYpHrh1IeTDTMzM2tl40idcreIiA0i4syiA2pB40jlSOsXHUiDm0jqi9HTZIMeblsoJxtmZmbWysaRhi5ds+hAWljT3gjXUx5+eRI9+56eBt7o4baFcrJhZmZmrcw3wrX3BGm4V3/HCzcO2FJSt+7B80AJD9OE37GTDTMzM2tlU0gTqjXdTVqzyJMfPoK/4654mDSC1To92HYcsEke6KBpONkwMzOzlhURH5CGFN2y6Fha3Dhgc0kDig6kwfW2k3g/0lwgTcPJhpmZmbU6j5ZUe6WO+E03WlKdPUaaFLDPdBJ3smFmZmatzqMl1V5T3gjXW0TMBR6lB99TRLwIvNiTbYvkZMPMzMxanW+Ea+8ZYDr+jrtiHLCFpP493LapvmMnG2ZmZtbqngRm0mQ3ac2kmUdLKsA4YBCwcQ+3XU/S0OqGVDtONszMzKylebSkuhkHbNxsoyUVoLedxAFGVimWmnOyYWZmZn3BOGC4R0uqqdJoSVsUHUiD+yfwFj1LNh7OfzdN4uxkw8zMzPqCccAAYNOiA2lh7hvTBRExnx6WnEXEG8BTPdm2KE42zMzMrC/wjXCNRcRLwAv4O+6KccCmkgb2cNum+Y6dbJiZmVlf8CweLakemupGuEDjgP70bIK+ccBqklasbki14WTDzMzMWl4eLck3wrU3Dli3mUZLKkg1Ook3xbXsZMPMzMz6itJoSYsXHUgLK90Ib1loFI3veeAVepYwPArM7+G2dedkw8zMzBqepJntfj5S0jnd3M04YC6wbi9juVDSAb3ZRzORFJLOKvv5W5JO62D1R0g3wuvUI7ZGIelOSR9vt+xESRdIuqrd8v1ICcMgYH9JEyTNl7R3Vz4rImYC/wDWarffYZKm9OpAasDJhpmZmfUVfwWWiIgJXd2gh7M8t5rZpJvi5Ra2Yh4taamIOK+0rI98h5cCB7dbdjBwQUQskJhGxLURMRxYBVgCGA3cS7o+u+qjEXFYV1Ys+vvvCyffzMzMWpikYcD5wHLAa8AXSaMi/ZP09HcpUufwXSPiHkn3AEcDSwO/BAYCs4AvRsSTko4E9geGAP0k7QKcDewJ/Bv4oE6H1ijmAr8FvgH8T/kblb77iPiXpAuB90lzbtwv6W1gTdL5WD3v66PA3qRztU9EzKnDsdTKVcAPJQ2IiA/y9/IR4N+SpkTEJvm62hcYDKwNXAv8HjgV+A4wXtLaQADPAT8A9gJGABsA95ASlBeATwNIGkn6/gFuLQVT4Rr+JHA96ZpfFDglIq6vxRfRnls2zMzMrBkMyuUmEyRNAP5f2XtnAxdFxGbAn4Bf5VnDnwQ2AnYAxgM7SloMWC0ipgFPADtGxBakG74zyvY5AjggInYG9gPWz/s6HNiulgfaoM4FDpW0VLvlH/ruy95bFdguIk7KP68N7Ea64f4jcGdEbEpK9D5Zy+BrLbfojCUlT5BaNa4gJQ7lhgMHkeZ7OQi4EjiNdO0dQEomhgG7AucBdwCfITUQrA9sDcwAPpv3dwFwfERsXiGs8mv4fWC/iBiR932WJPXmmLvKLRtmZmbWDGbl0hPgP09uS52QtyU9xQW4BPhxfn0vsBPpifqZwJeBu2nrxLwUcJGkdUk3hYuWfd5t+QaSvI9LcwLzoqQ7qnhcTSEi3pZ0MfB1UnJQ0tF3D3Bl/s5K/hIRcyRNJs00fktePpl0g93sSqVU1+e/j66wzu0R8RaApLnAi6SO4veQWjN+Trre5gNDgVPy63mASK1CjwDD8ohfQyPinrzvS2hLdmDBa1jAGZJK+14FWBF4ufeH3Tm3bJiZmVmrugfYkfQ0+GbSzdsupCQEUpnKnRGxCbAPqZyq5N36hdk0fkG6ge7qaF7tv8PZ8J8ZtOfk4Ygh3fy2wgPw64HdJY0ABkfEIxXWmQ2QS/NWYsGWoEOB5YGRObGeA4wCPgFMi4jVI+IfpMSjK99X+fffft+vsOD1XjNONszMzKzZPUBb59xDaUsmxpJKnuZHxPvABOBYUhICqWXjhfz6yE72fw9wkKR+klYmlaH0Ofkp+RUs+MS+o+++z8mjRN1J6kNxaUfrSVqaVP70KKmV6CHaWuBeBZaQtCswADiibLst2n3eDGCGpB3yokM7CW8p4NXcsrQrsEb3jq7nnGyYmZlZszse+KKkScBhwAkAETGb1KH7obzevaTRfybnn38MnCnpUTp/UnwtMA14HLgYeLDaB9BEziJ1Bi9p/92fLulhUrlPX3QpsDmdJBvAccAKpH4bvwduIw06cDhwFKmc6nBSn6P+pHKzdUgtce19ETg392PqrA/Gn4Atcwnb4aT+SnWhthYsMzMzM7OekzQEeAf474j48cLWt9bnlg0zMzMzq4pcSvQ2qQOymZMNMzMzM6uqF0hzTJg52TAzMzOzqnoRt2xY5mTDzMzMzKrpRdyyYZmTDTMzMzOrpheAj0jyfaY52TAzMzOzqnqRNBv7skUHYsVzsmFmZmZm1VSaKNH9NszJhpmZmZlV1Yv5b/fbMCcbZmZmZlZVbtmw/3CyYWZmZmbV9DIQuGXDcLJhZmZmZlUUEXOAV3HLhuFkw8zMzMyqz3NtGOBkw8zMzMyq7wXcsmE42TAzMzOz6nPLhgFONszMzMys+l4AVpA0oOhArFhONszMzMys2kpzbaxUaBRWOCcbZmZmZtYpSatKul7SNElPSfrlQlotSsnGQvttSHpW0nLVidQajZMNMzMzM+uQJAHXANdFxLrAesAQ4PRONpsGXAXMUuJ7zj7KJ97MzMzMOrMb8H5EXAAQEfOAbwBHSRqVWzzuyq0e38vbzAE2A04CpgCrSfq1pIclPSbp++0+43hJ4yVNlrRBnY7L6qB/0QGYmZmZWUPbGHikfEFEvC3pX6R7ya2BTYD3gHGSbgJeB9YFjoiIhwAk/U9EvCGpH3C7pM0iYlLe5esRMULSKOBbwJfqcmRWc27ZMDMzM7PeuC0ipkfELFK51Q55+XOlRCP7nKTxwKOkBGajsveuyX8/AgyrcbxWR042zMzMzKwzjwMjyxdIWhJYHZgLRLv1Sz+/W7b+mqQWi90jYjPgJmBg2Taz89/zcOVNS3GyYWZmZmaduR0YLOlwgFwGdRZwIal0ak9Jy0gaBHwGuL/CPpYkJR9vSVoR2LsegVvxnGyYmZmZWYciIoD9gAMlTQOmAu8D382rjAWuBiYBV0fEwxX2MZFUPvUE8GcqJyTWgpSuHzMzMzOz7pF0JLBlRHyt6FisMbllw8zMzMzMasItG2ZmZmZmVhNu2TAzMzMzs5pwsmFmZmZmZjXhZMPMzMzMzGrCyYaZmZmZmdWEkw0zMzMzM6sJJxtmZmZmZlYTTjbMzMzMzKwm/j962vuwK1fMPwAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 1008x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Testing out insert on the family tree from homework 9\n",
    "people1 = ['Bob','Alice','Doug','Kathy','Queen','Carol','Irene','Tom',\n",
    "           'Peter','Wanda','Yaakov', 'Luis','Zandra','Ronald','Mabel','Ursala','Eve',\n",
    "           'Frank','Ginger','Norm','Sarah','Jeff','Vince','Howard',\n",
    "           'Oprah']\n",
    "\n",
    "rbt = RBT()\n",
    "bst = BST()\n",
    "for p in people1:\n",
    "    bst.insert(p)\n",
    "    rbt.insert(p)\n",
    "\n",
    "print(rbt.tree.traverse_infix())\n",
    "print(bst.tree.traverse_infix())\n",
    "\n",
    "plot_tree(bst.tree, figsize=(14,4))\n",
    "plot_tree(rbt.tree, figsize=(14,4))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Testing out delete on the family tree from homework 9\n",
    "people1 = ['Bob','Alice','Doug','Kathy','Queen','Carol','Irene','Tom',\n",
    "           'Peter','Wanda','Yaakov', 'Luis','Zandra','Ronald','Mabel','Ursala','Eve',\n",
    "           'Frank','Ginger','Norm','Sarah','Jeff','Vince','Howard',\n",
    "           'Oprah']\n",
    "\n",
    "rbt = RBT()\n",
    "for p in people1:\n",
    "    rbt.insert(p)\n",
    "\n",
    "plot_tree(rbt.tree, figsize=(10,2))\n",
    "rbt.delete('Mabel')\n",
    "plot_tree(rbt.tree, figsize=(10,2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Sorted data in a BST vs. RBT\n",
    "*Note the BST has a depth of nine vs. the RBT which has a depth of 3*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Compare worst case insert in BST to how it is handled in RBT\n",
    "rbt2 = RBT()\n",
    "bst2 = BST()\n",
    "for i in range(10):\n",
    "    rbt2.insert(i)\n",
    "    bst2.insert(i)\n",
    "plot_tree(bst2.tree, figsize=(10,5))\n",
    "plot_tree(rbt2.tree, figsize=(10,5))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
